package leetcode;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-23 17:43
 **/
public class LeetCode5973 {

    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

    public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {
        int m = grid.length;
        int n = grid[0].length;
        //arr[0]: 距离
        //arr[1]: 价格
        //arr[2]: x
        //arr[3]: y
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] != b[1] ? a[1] - b[1] : a[2] != b[2] ? a[2] - b[2] : a[3] - b[3]);
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{start[0], start[1]});
        Set<Integer> visited = new HashSet<>();
        int x = start[0];
        int y = start[1];
        visited.add(x * 10001 + y);
        int v = grid[x][y];
        if (v != 0 && v != 1 && v >= pricing[0] && v <= pricing[1]) {
            pq.offer(new int[]{0, grid[x][y], x, y});
        }
        int step = 0;
        while (!q.isEmpty()) {
            //步数+1
            ++step;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] poll = q.poll();
                x = poll[0];
                y = poll[1];

                for (int[] dir : dirs) {
                    int x1 = x + dir[0];
                    int y1 = y + dir[1];
                    if (x1 >= 0 && x1 < m && y1 >= 0 && y1 < n && grid[x1][y1] != 0 && visited.add(x1 * 10001 + y1)) {
                        q.add(new int[]{x1, y1});
                        v= grid[x1][y1];
                        if (v != 1 && v >= pricing[0] && v <= pricing[1]) {
                            pq.offer(new int[]{step, grid[x1][y1], x1, y1});
                        }
                    }
                }
            }
        }

        List<List<Integer>> res = new ArrayList<>();
        while (!pq.isEmpty() && --k >= 0) {
            int[] poll = pq.poll();
            res.add(Arrays.asList(poll[2], poll[3]));
        }

        return res;
    }

}
